package 中等.二分查找;

/**
 * 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
 * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
 */
public class 有序数组中的单一元素_540 {

    public static void main(String[] args) {

        //1,2,3,4,5,6
        int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
        int i = singleNonDuplicate2(nums);
        System.out.println(i);

    }

    public static int singleNonDuplicate(int[] nums) {
        //定义左右边界
        int left = 0, right = nums.length - 1;
        int mid;
        //[left,right)，当剩下一个元素时停止循环
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == nums[mid + 1]) {
                if (mid % 2 == 0) {
                    left = mid + 2;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid] == nums[mid - 1]) {
                if ((mid + 1) % 2 == 0) {
                    left = mid + 1;
                } else {
                    right = mid - 2;
                }
            } else {
                return nums[mid];
            }
        }
        //如果剩下一个元素，直接返回剩下的那一个元素
        return nums[left];
    }

    //将首尾是唯一元素的情况直接返回，稍微减少时间和空间，mid两边是奇数个数那一边的存在唯一元素
    public static int singleNonDuplicate1(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        //如果开头是那个唯一元素，那么剩下num[(mid=0)-1]会有数组越界异常
        if (nums[0] != nums[1]) {
            return nums[0];
        }
        //如果结尾是那个唯一元素，那么剩下num[(mid=nums.length-1)+1]会有数组越界异常
        if (nums[nums.length - 1] != nums[nums.length - 2]) {
            return nums[nums.length - 1];
        }
        //定义左右边界
        int left = 0, right = nums.length - 1;
        int mid;
        //[left,right]
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == nums[mid + 1]) {
                if (mid % 2 == 0) {
                    left = mid + 2;
                } else {
                    right = mid - 1;
                    System.out.println();
                }
            } else if (nums[mid] == nums[mid - 1]) {
                if ((mid + 1) % 2 == 0) {
                    left = mid + 1;
                } else {
                    right = mid - 2;
                    System.out.println();
                }
            } else {
                return nums[mid];
            }
        }
        return -1;
    }

    /**
     * 已经是有序数组，无需排序
     * 二分查找，如果找到，nums[i]!=nums[i+1]!=nums[i-1]停止
     * 左右边界缩减：因为每个元素都会出现两次，2,2...,如果右边的元素数量是偶数，那么右边的元素可以排除
     *
     * @param nums
     * @return
     */
    public static int singleNonDuplicate2(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        if (length > 1 && nums[0] != nums[1]) {
            return nums[0];
        }
        if (length > 1 && nums[length - 1] != nums[length - 2]) {
            return nums[length - 1];
        }
        int left = 1, right = length - 2;
        while (left < right) {  //最后剩下的left=right即为答案
            int mid = left + (right - left) / 2;
            if (nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1]) {
                return nums[mid];
            } else if (nums[mid] == nums[mid + 1] && (length - mid) % 2 == 0) {
                right = mid - 1;
            } else if (nums[mid] == nums[mid - 1] && (length - 1 - mid) % 2 == 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }

}
